#include <iostream>
#include <vector>
using namespace std;

// class InsertionSort {
// public:
//   static void insertionSort(vector<int> &v) {
//     /**
//      * j: 用来记录已排序的序列的最后一个下标
//      * x: 代表待插入数据
//      */
//     int j = 0, x = v[0];
//     for (int i = 1; i < v.size(); ++i) {
//       j = i - 1, x = v[i];
//       while (v[j] > x && j >= 0) {
//         v[j + 1] = v[j];
//         j--;
//       }
//       v[j + 1] = x;
//     }
//   }
// };
// class InsertionSort {
// public:
//   static void insertionSort(vector<int> &v) {
//     /**
//      * "哨兵版本"，v[0] 为 "哨兵", v[1] ~ v[n] 为待排序元素
//      */
//     for (int i = 2; i < v.size(); ++i) {
//       v[0] = v[i];
//       int j = i - 1;
//       //
//       如果待插入元素甚至比前面的一个元素还要大，那么我们不需要进行后面的移位操作
//       if (v[0] < v[j]) {
//         for (; j >= 0 && v[j] > v[0]; --j) {
//           v[j + 1] = v[j];
//         }
//       }
//       v[j + 1] = v[0];
//     }
//   }
// };
// class InsertionSort {
// public:
//   static void insertionSort(vector<int> &v) {
//     for (int i = 1; i < v.size(); ++i) {
//       // x 代表要插入的元素
//       int x = v[i];
//       // low ~ high 代表有序序列的范围
//       int low = 0, high = i - 1, mid;
//       // 下面的算法用于实现查找第一个大于 x 的元素的索引位置，实质就是
//       // upper_bound 的实现，最后的 low 就是想要的索引下标
//       while (low + 1 != high) {
//         int mid = low + (high - low) >> 1;
//         if (v[mid] > x)
//           high = mid;
//         else
//           low = mid;
//       }
//       for (int j = high; j < i - 1; ++j)
//         v[j + 1] = v[j];
//       v[high] = x;
//     }
//   }
// };
class InsertionSort {
public:
  void insertionSort(vector<int> &v) {
    int d[3] = {5, 3, 1}, len = 3;
    for (int i = 0; i < len; ++i) {
      shellInsert(v, d[i]);
    }
  }

  void shellInsert(vector<int> &v, int delta) {
    for (int i = delta; i < v.size(); ++i) {
      int x = v[i], j = i - delta;
      while (j >= 0 && x < v[j]) {
        v[j + delta] = v[j];
        j -= delta;
      }
      v[j + delta] = x;
    }
  }
};

int main() {
  vector<int> v{0, 3, 10, 2, 99, -1, 999, 121, -2, 0, 0, -1, 99, 777};
  InsertionSort *algo = new InsertionSort;
  algo->insertionSort(v);
  for (auto &i : v) {
    cout << i << " ";
  }
  return 0;
}